|
Jacobi symbol (m/n) for various ''m'' (along top) and ''n'' (along left side). Only 0 ≤ ''m'' < ''n'' are shown, since due to rule (2) below any other ''m'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of -1 is a quadratic residue, and if m is a quadratic residue (mod n) and gcd(m,n)=1, then (m|n)=1, but some entries with a Jacobi symbol of 1 (see the ''n''=9 row) are not quadratic residues. Notice also that when either ''n'' or ''m'' is a square, all values are 0 or 1. The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837,〔C.G.J.Jacobi "Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie", ''Bericht Ak. Wiss. Berlin'' (1837) pp 127-136.〕 it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography. ==Definition== For any integer and any positive odd integer the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of : : represents the Legendre symbol, defined for all integers and all odd primes by : Following the normal convention for the empty product, The Legendre and Jacobi symbols are indistinguishable exactly when the lower argument is an odd prime, in which case they have the same value. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Jacobi symbol」の詳細全文を読む スポンサード リンク
|